import java.util.Stack;

public class FindZZ_0315 {
//      class TreeNode {
//            int val;
//            TreeNode left;
//            TreeNode right;
//            TreeNode(int x) { val = x; }
//     }


    /*第二种方法
     */
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == null) return null;
//        Stack<TreeNode> stackP = new Stack<>();
//        Stack<TreeNode> stackQ = new Stack<>();
//        getPath(root,p,stackP);
//        getPath(root,q,stackQ);
//        int sizeP = stackP.size();
//        int sizeQ = stackQ.size();
//        if (sizeP > sizeQ) {
//            int size = sizeP - sizeQ;
//            while (size != 0) {
//                stackP.pop();
//                size--;
//            }
//        }
//        if (sizeP < sizeQ) {
//            int size = sizeQ - sizeP;
//            while (size != 0) {
//                stackQ.pop();
//                size--;
//            }
//        }
//        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
//            if (stackP.peek().equals(stackQ.peek())) return stackP.peek();
//            stackP.pop();
//            stackQ.pop();
//        }
//        return null;
//    }
//    private boolean getPath (TreeNode root, TreeNode node, Stack<TreeNode> stack) {
//          if (root == null || node == null) return false;
//          stack.push(root);
//          if (root == node) return true;
//          boolean leftget = getPath(root.left,node,stack);
//          if (leftget) return true;
//          boolean rightget = getPath(root.right,node,stack);
//          if (rightget) return true;
//          stack.pop();
//          return false;
//    }



  /*第一种方法
    */

//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//          if (root == null) return null;
//          if (p == root || q == root) return root;
//          if (p.val < root.val && q.val > root.val || q.val < root.val && p.val > root.val) return root;
//          TreeNode left = lowestCommonAncestor(root.left,p,q);
//          TreeNode right = lowestCommonAncestor(root.right,p,q);
//          if (left != null && right != null) {
//              return root;
//          } else if (left != null) {
//              return left;
//          }else {
//              return right;
//          }
//    }
}
